class Solution:
    def mincostTickets(self, days: list, costs: list) -> int:
        dp = [2**31 for _ in range(366)]
        dp[0] = 0
        days_set = set(days)
        cost_dict = {1: costs[0], 7: costs[1], 30: costs[2]}
        for i in range(1, 366):
            if i in days_set:
                for day, cost in cost_dict.items():
                    d = i - day if i - day > 0 else 0
                    dp[i] = min(dp[i], dp[d] + cost)
            else:
                dp[i] = dp[i - 1]

        return dp[days[-1]]
